import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;

/**
 * @ClassName Offer57
 * @Description 剑指 Offer 57. 和为s的两个数字
 * @Author clockTown
 * @Date 2021/8/24 9:38
 * @Version 1.0
 */
class Offer57 {
}

/**
 * v0 list 超时
 */
class Offer57V0 {
    public int[] twoSum(int[] nums, int target) {
        List<Integer> list = new ArrayList<>();
        for (int num : nums) {
            if (list.contains(target - num)){
                return new int[]{num, target-num};
            }
            list.add(num);
        }

        return null;
    }
}

/**
 * v1 hashMap
 */
class Offer57V1 {
    public int[] twoSum(int[] nums, int target) {
        HashMap<Integer,  Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            int num = nums[i];
            if (map.containsKey(target - num)){
                return new int[]{num, target - num};
            }
            map.put(num, i);

        }
        return null;
    }
}

/**
 * v2 二分查找(超时)
 */
class Offer57V2 {
    public int[] twoSum(int[] nums, int target) {
        for (int num : nums) {
            if (binarySearch(nums, target - num)){
                return new int[]{num, target - num};
            }
        }
        return null;
    }

    private boolean binarySearch(int[] nums, int target){
        int l = 0;
        int r = nums.length - 1;
        while (l < r){
            int mid = (l + r) >> 2;
            if (nums[mid] == target){
                return true;
            }
            if (nums[mid] < target){
                l = mid + 1;
            }else {
                r = mid - 1;
            }
        }
        return false;
    }
}

/**
 * v3 二分查找+双指针
 */
class Offer57V3 {
    public int[] twoSum(int[] nums, int target) {
        //二分查找
        int index = binarySearch(nums,target);
        int i = 0,j = index;
        while (i < j){
            while (i < j &&nums[i]+nums[j] > target) {
                j--;
            }
            while (i < j && nums[i]+nums[j] < target) {
                i++;
            }
            if(nums[i]+nums[j] == target) {
                return new int[]{nums[i],nums[j]};
            }
        }

        return new int[0];
    }

    private int binarySearch(int[] nums, int target) {
        int mid;
        int start = 0;
        int end = nums.length-1;
        while (end -start >= 1) {
            mid = (start+end)/2;
            if(nums[mid] > target) {
                end = mid-1;
            }else {
                start = mid+1;
            }
        }
        return start;
    }
}

